package com.itzmn.newcode.offer;

import java.util.Stack;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/15 13:40
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer
 *    判断一组数据，是否是前一个数据组成的栈的弹出序列
 *    思路：
 *     使用栈， 将弹出序列的第一个数据得到，然后将栈数据压入，一直压到该数据，然后弹出，记录当前压入数据的位置
 *     ，然后查看第二个被弹出的数据，比较该数据在真实数据中的索引是否大于刚刚记录的位置，如果大于将该段中的数据压入栈中，
 *     如果不是弹出数据，与该数据比较
 *
 */
public class IsStackPopOrder {


    public static void main(String[] args) {

        int[] ints = {1};
        int[] ints1 = {2};

        new IsStackPopOrder().IsPopOrder(ints,ints1);
    }

    public boolean IsPopOrder(int [] pushA,int [] popA) {

        Stack<Integer> stack = new Stack<>();

        int start = popA[0];

        int index = 0;
        for (int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            if (pushA[i] == start){
                index = i;
                break;
            }
        }

        Integer pop1 = stack.pop();
        if (pop1 != start){
            return false;
        }
        // 已经将第一个弹出的数据的前面数据全部压入栈中。

        //判断后面每个数据
        for (int i=1;i<popA.length;i++){

            for (int j=0;j<pushA.length;j++){

                if (pushA[j] == popA[i]){

                    if (j<index){
                        Integer pop = stack.pop();
                        if (pop == popA[i]){
                            break;
                        }else {
                            return false;
                        }
                    }
                    if (j>index){
                        for (int m=index+1;m<=j;m++){
                            stack.push(pushA[m]);
                        }
                        index = j;
                        stack.pop();
                    }
                }
            }
        }
        return true;
    }



}
